package com.LeeCode;

/**
 * 前序遍历构造二叉搜索树
 */

public class Code1008 {
    public static void main(String[] args) {
        int[] preorder = {8, 5, 1, 7, 10, 12};
        new Code1008().bstFromPreorder(preorder);
    }

    private int idx = 0;
    private int[] preorder;

    public TreeNode bstFromPreorder(int[] preorder) {
        this.preorder = preorder;
        return build(Integer.MIN_VALUE, Integer.MAX_VALUE);
    }

    private TreeNode build(int minVal, int maxVal) {
        if (idx == preorder.length) return null;
        int val = preorder[idx];

        // 不属于当前子树范围，返回 null
        if (val < minVal || val > maxVal) return null;

        TreeNode node = new TreeNode(val);
        idx++;

        // 构建左右子树
        node.left = build(minVal, val);
        node.right = build(val, maxVal);

        return node;
    }
}
